package likou.offer;

import java.util.Arrays;

/**
 * @Info: 重建二叉树
 * @Author: 唐小尊
 * @Date: 2020/8/2  14:03
 */
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class _07 {

    public TreeNode buildTree(int[] preorder, int[] inorder) {

        if (preorder.length == 0 || preorder.length != inorder.length) {
            return null;
        }

        TreeNode root = new TreeNode(preorder[0]);
        if (preorder.length != 1) {
            int leftNum = 0;
            for (int i = leftNum; i < inorder.length; i++) {
                if (preorder[0] == inorder[i]) {
                    leftNum = i;
                    break;
                }
            }
            root.left = buildTree(Arrays.copyOfRange(preorder, 1, 1 + leftNum),
                    Arrays.copyOfRange(inorder, 0, leftNum));
            root.right = buildTree(Arrays.copyOfRange(preorder, 1 + leftNum, preorder.length),
                    Arrays.copyOfRange(inorder, 1 + leftNum, inorder.length));
        }
        return root;
    }


    public TreeNode buildTree1(int[] preorder, int[] inorder) {
        if (preorder.length == 0 || preorder.length != inorder.length) {
            return null;
        }
        TreeNode treeNode = new TreeNode(preorder[0]);
        int leftNum = 0;
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == preorder[0]) {
                leftNum = i;
                break;
            }
        }
        treeNode.left = buildTree1(Arrays.copyOfRange(preorder, 1, leftNum + 1), Arrays.copyOfRange(inorder, 0, leftNum));
        treeNode.right = buildTree1(Arrays.copyOfRange(preorder, leftNum + 1, preorder.length), Arrays.copyOfRange(inorder, leftNum + 1, inorder.length));
        return treeNode;
    }


    public static void main(String[] args) {
        buildTree2(new int[]{3, 9, 20, 15, 7}, new int[]{9, 3, 15, 20, 7});
    }

    private static int in = 0;
    private static int pre = 0;

    public static TreeNode buildTree2(int[] preorder, int[] inorder) {
        return build(preorder, inorder, Integer.MIN_VALUE);
    }

    private static TreeNode build(int[] preorder, int[] inorder, int stop) {
        //如果当前的前序数组已经全部遍历完成，则返回null
        if (pre >= preorder.length) {
            return null;
        }
        //表示找到当前最左边的，中序遍历的数组下标就往后一位
        if (inorder[in] == stop) {
            in++;
            return null;
        }

        //直接一次性搞定，找到最左边的，深度查找
        TreeNode node = new TreeNode(preorder[pre++]);
        node.left = build(preorder, inorder, node.val);
        node.right = build(preorder, inorder, stop);
        return node;
    }
}
